Skip to content

Latest commit

 

History

History
71 lines (57 loc) · 1.85 KB

README.md

File metadata and controls

71 lines (57 loc) · 1.85 KB

501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

 1 \ 2 / 2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solutions (Python)

1. Inorder Traversal

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: deffindMode(self, root: TreeNode) ->List[int]: nodes= [] curr=rootprev=0cnt=0max_cnt=1modes= [] whilenodesorcurr: whilecurr: nodes.append(curr) curr=curr.leftcurr=nodes.pop() ifcurr.val==prev: cnt+=1else: ifcnt==max_cnt: modes.append(prev) elifcnt>max_cnt: modes= [prev] max_cnt=cntprev=curr.valcnt=1curr=curr.rightifcnt==max_cnt: modes.append(prev) elifcnt>max_cnt: modes= [prev] returnmodes
close